using System.Collections.Generic;
using System;


namespace Mono.Boost.Graph
{


    public struct Pair<T, U>
    {
        public Pair(T t, U u)
        {
            first = t;
            second = u;

        }
        public T first;
        public U second;
    }

    public class StaticGraph : IGraph
    {
        uint _ec, _vc;
        uint[][] _vtab;
        uint[] _etab;

        public StaticGraph(uint n, Pair<uint, uint>[] edges)
        {
            _vc = n;
            _ec = (uint)edges.Length;
            _vtab = new uint[_vc][];
            _etab = new uint[_ec];

            //table with needed sizes of outgoing edges
            uint[] tab = new uint[_vc];

            for (uint i = 0; i < _ec; i++)
                tab[edges[i].first]++;
            for (uint i = 0; i < _vc; i++)
            {
                _vtab[i] = new uint[tab[i]];
                tab[i] = 0;
            }

            for (uint i = 0; i < _ec; i++)
            {
                _etab[i] = edges[i].second;
                _vtab[edges[i].first][tab[edges[i].first]++] = i;
            }
        }
        public uint verticesCount { get { return _vc; } }
        public uint edgesCount { get { return _ec; } }
        public uint highestVertexId { get { return _vc - 1; } }
        public uint highestEdgeId { get { return _ec - 1; } }
        public IEnumerable<EdgeFullInfo> edges
        {
            get
            {
                for (uint i = 0; i < _vc; i++)
                    foreach (uint e in _vtab[i])
                        yield return new EdgeFullInfo(i, _etab[e], e);
            }
        }

        public IEnumerable<uint> vertices
        {
            get
            {
                for (uint i = 0; i < _vc; i++)
                    yield return i;
            }
        }
        public IEnumerable<EdgeInfo> outgoing(uint v)
        {
            foreach (uint e in _vtab[v])
                yield return new EdgeInfo(_etab[e], e);
        }
        public IEnumerable<EdgeInfo> incoming(uint v)
        {
            for (uint i = 0; i < _vc; i++)
                foreach (uint e in _vtab[i])
                    if (_etab[e] == v)
                        yield return new EdgeInfo(i, e);
        }
        public StaticPropertyMap<T> createEdgePropertyMap<T>()
        {
            return new StaticPropertyMap<T>(edgesCount);
        }
        public StaticPropertyMap<T> createVertexPropertyMap<T>()
        {
            return new StaticPropertyMap<T>(verticesCount);
        }
        public uint edge_destination(uint id)
        {
            return _etab[id];
        }
        public uint edge_source(uint id)
        {
            for (uint i = 0; i < _vc; i++)
                foreach (uint e in _vtab[i])
                    if(e == id)
                        return i;
            throw new ArgumentException("No edge with this id");
        }
    }
}
